{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Color the Triangle Red"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: colorRed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #把三角形染成红色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定你一个整数 <code>n</code> 。考虑一个边长为 <code>n</code> 的等边三角形，被分成 <code>n<sup>2</sup></code> 个单位等边三角形。这个三角形有 <code>n</code> 个 <strong>从 1 开始编号</strong> 的行，其中第 <code>i</code> 行有 <code>2i - 1</code> 个单位等边三角形。</p>\n",
    "\n",
    "<p>第 <code>i</code> 行的三角形也是&nbsp;<strong>从 1 开始编号&nbsp;</strong>的，其坐标从 <code>(i, 1)</code> 到 <code>(i, 2i - 1)</code>&nbsp;。下面的图像显示了一个边长为 <code>4</code> 的三角形及其三角形的索引。</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/01/triangle4.jpg\" style=\"width: 402px; height: 242px;\" />\n",
    "<p>如果两个三角形 <strong>共享一条边</strong> ，则它们是 <strong>相邻</strong> 的。例如：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>三角形 <code>(1,1)</code> 和 <code>(2,2)</code> 是相邻的。</li>\n",
    "\t<li>三角形 <code>(3,2)</code> 和 <code>(3,3)</code> 是相邻的。</li>\n",
    "\t<li>三角形 <code>(2,2)</code> 和 <code>(3,3)</code> 不相邻，因为它们没有共享任何边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>初始时，所有单位三角形都是 <strong>白色</strong> 的。你想选择 <code>k</code> 个三角形并将它们涂成 <strong>红色</strong> 。然后我们将运行以下算法：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选择一个 <strong>至少有两个</strong> 红色相邻三角形的白色三角形。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>如果没有这样的三角形，请停止算法。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>将该三角形涂成 <strong>红色</strong> 。</li>\n",
    "\t<li>回到步骤 1。</li>\n",
    "</ol>\n",
    "\n",
    "<p>选择最小的 <code>k</code> 并在运行此算法之前将 <code>k</code> 个三角形涂成红色，使得在算法停止后，所有单元三角形都被涂成红色。</p>\n",
    "\n",
    "<p>返回一个二维列表，其中包含你要最初涂成红色的三角形的坐标。答案必须尽可能小。如果有多个有效的解决方案，请返回其中任意一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/01/example1.jpg\" style=\"width: 500px; height: 263px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 3\n",
    "<b>输出：</b>[[1,1],[2,1],[2,3],[3,1],[3,5]]\n",
    "<b>解释：</b>初始时，我们选择展示的5个三角形染成红色。然后，我们运行以下算法：\n",
    "- 选择(2,2)，它有三个红色相邻的三角形，并将其染成红色。\n",
    "- 选择(3,2)，它有两个红色相邻的三角形，并将其染成红色。\n",
    "- 选择(3,4)，它有三个红色相邻的三角形，并将其染成红色。\n",
    "- 选择(3,3)，它有三个红色相邻的三角形，并将其染成红色。 \n",
    "可以证明，选择任何4个三角形并运行算法都无法将所有三角形都染成红色。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/09/01/example2.jpg\" style=\"width: 300px; height: 101px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>n = 2\n",
    "<b>输出：</b>[[1,1],[2,1],[2,3]]\n",
    "<b>解释：</b>初始时，我们选择图中所示的 3 个三角形为红色。然后，我们运行以下算法： \n",
    "-选择有三个红色相邻的 (2,2) 三角形并将其染成红色。 \n",
    "可以证明，选择任意 2 个三角形并运行该算法都不能使所有三角形变为红色。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [color-the-triangle-red](https://leetcode.cn/problems/color-the-triangle-red/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [color-the-triangle-red](https://leetcode.cn/problems/color-the-triangle-red/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorRed(self, size: int) -> List[List[int]]:\n",
    "        n, res_l = 2 * size, []\n",
    "        for i in range(size, 1, -4):\n",
    "            res_l += [[i, j] for j in range(1, n, 2)]\n",
    "            if i >= 3: res_l.append([i - 1, 2])\n",
    "            i -= 2\n",
    "            if i >= 2: res_l += [[i, j] for j in range(3, n - 4, 2)]\n",
    "            if i >= 3: res_l.append([i - 1, 1])\n",
    "            i -= 2\n",
    "            n -= 8\n",
    "        res_l.append([1, 1])\n",
    "        return res_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorRed(self, size: int) -> List[List[int]]:\n",
    "        n, res_l = 2 * size, []\n",
    "        for i in range(size, 1, -4):\n",
    "            res_l += [[i, j] for j in range(1, n, 2)]\n",
    "            if i >= 3: res_l.append([i - 1, 2])\n",
    "            i -= 2\n",
    "            if i >= 2: res_l += [[i, j] for j in range(3, n - 4, 2)]\n",
    "            if i >= 3: res_l.append([i - 1, 1])\n",
    "            i -= 2\n",
    "            n -= 8\n",
    "        res_l.append([1, 1])\n",
    "        return res_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorRed(self, n: int) -> List[List[int]]:\n",
    "        res = [[1,1]]\n",
    "        p = 0\n",
    "        for r in range(n,1,-1):\n",
    "            if p == 0:\n",
    "                for c in range(1,r<<1,2):\n",
    "                    res.append([r,c])\n",
    "            elif p == 1:\n",
    "                res.append([r,2])\n",
    "            elif p == 2:\n",
    "                for c in range(3,r<<1,2):\n",
    "                    res.append([r,c])\n",
    "            else:\n",
    "                res.append([r,1])\n",
    "            p = (p+1)%4\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def colorRed(self, size: int) -> List[List[int]]:\n",
    "      n, res_l = 2 * size, []\n",
    "      for i in range(size, 1, -4):\n",
    "          res_l += [[i, j] for j in range(1, n, 2)]\n",
    "          if i >= 3: res_l.append([i - 1, 2])\n",
    "          i -= 2\n",
    "          if i >= 2: res_l += [[i, j] for j in range(3, n - 4, 2)]\n",
    "          if i >= 3: res_l.append([i - 1, 1])\n",
    "          i -= 2\n",
    "          n -= 8\n",
    "      res_l.append([1, 1])\n",
    "      return res_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [[],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def colorRed(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.colorRed(size - 4)\n",
    "        for i in range(size): res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2): res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
